public class Code1 {
    // 买卖股票的进阶问题

    public int maxProfit(int[] prices) {

        // 创建 dp 表
        // 初始化
        // 填表
        // 确定返回值

        // 首先创建出一个 dp 表
        // 简单分析题目，我们可以得知，这里有两种可能存在的状态：买入、卖出
        // 题目中还有一个限定条件是这里的交易不能超过 2 笔
        int n = prices.length;
        // f 表在这里表示的是，在第 i 天结束后完成了 j 次交易，此时处于“买入”状态下所能的到的最大利润
        int[][] f = new int[n][3];
        // g 表在这里表示的是，在第 i 天结束后完成了 j 次交易，此时处于“卖出”状态下得到的最大利润
        int[][] g = new int[n][3];

        // 实现初始化操作
        int INF = 0x3f3f3f3f;
        // 首先我们需要确保的是 f 表和 g 表的第一行中除了第一位元素外的值要均为负无穷
        for(int j=0; j < 3; j++){
            f[0][j] = g[0][j] = -INF;
        }
        // 针对 当天结束后 “买入” 状态下的初始化，买入后的利润就是股票当天价格的负值
        f[0][0] = -prices[0];
        // 针对 当天结束后 “卖出” 状态下的初始化，最开始时并没有任何股票在手中，此时初始化为 0
        g[0][0] = 0;

        // 进行填表操作
        // 这里的填表是 从上到下，从左向右依次填写的
        for(int i=1; i < n; i++){
            for(int j=0; j < 3; j++){
                // 针对当天最后状态为 “买入” 填表，有两种情况：从前一天到当天什么都不操作即为 f[i - 1][j]。从前一天为 “卖出” 的状态到今天最后为 “买入” 的状态，此时说明进行了 购入 操作，即利润为 -p[i]
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                // 针对当天的最后的状态为 “卖出” 填表，同样的有两种情况：从前一天开始就是卖出状态一直到当天结束不进行操作。前一天为 “买入” 状态，当天进行卖出，当日结束时处于 “卖出” 状态，此时利润为 +p[i]

                // 还需要注意的是，这里的交易次数限制不能超过 2 次。对此我们以 卖出 作为一个节点在这里执行 交易次数 + 1 即就是 j + 1
                // 理论上，g 表所获取的利润值式子如下，但是需要注意的是 j - 1 的值必须大于 0。这里的式子在控制 j 时会影响到其正确值。
                // g[i][j] = Math.max(g[i - 1][j], f[i - 1][j - 1] + prices[i])
                // 对此，调整如下
                g[i][j] = g[i - 1][j];
                if(j-1 >= 0){
                    // 这样来确保最大利润
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ret = 0;
        // 我们需要知道在执行 卖出 操作后获取的利润一定为 +prices
        // 所以我们这里直接 遍历 g 表最后一行获取最大值即可
        for(int i = 0; i < 3; i++){
            ret = Math.max(ret, g[n - 1][i]);
        }
        return ret;
    }
}
